package algorithm.leetcode.I1to100;


/**
 * 这题的核心是要想清楚,由于不存在重复数字,二分法也是可以用的
 * 旋转数组随便切割,取出中间的任意一段也是旋转数组
 * 只是比普通的二分法多一步考虑在左右哪边
 *
 * 但是如果包含重复数字,那么参见剑指offer SQ11题 暴力法与二分法交替使用
 */

public class Q33 {

    public static void main(String[] args) {
        Q33 threeThree = new Q33();
        System.out.println(threeThree.search(new int[]{1,3}, 1));
    }

    public int search(int[] nums, int target) {

        if (nums.length == 0) return -1;

        int low = 0, high = nums.length-1;
        int mid;

        while (low <= high) {

            mid = low + (high-low)/2;
            // 搜索终止条件
            if (nums[mid] == target) return mid;

            // 右半边顺序并且在右半边
            if (nums[mid] <= nums[high]) {
                // 在右半边
                if (nums[mid] <= target && target <= nums[high]) low = mid + 1;

                // 不在右半边,在左半边
                else high = mid - 1;
            }

            // 左半边顺序
            else {

                // 在左半边
                if (nums[low] <= target && target <= nums[mid]) high = mid - 1;

                // 不在左半边,在右半边
                else low = mid + 1;

            }

        }
        return -1;

    }
}
